package TreeMap;

//实现一个哈希桶

import BinarySearchTree.BinarySearchTree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class HashBuck {

    static class Node {
        public int key;

        public int val;

        public Node random;
        public Node next;
        //构造
        public Node(int key,int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] array;//定义一个存储节点的数组

    public int useSize;//数组的当前大小

    //定义一个负载因子（常量）
    public static final double LOAD_FCTOR = 0.75;
    public Node next;//数组中每一个下标都是一个链表，存放的是链表的头节点

    public HashBuck() {//构造   初始化外部类的数组给一个长度，useSize不用初始化，默认存放的就是0
        array = new Node[10];
    }
    public void put(int key,int val) {
        int index = key % array.length;  //首先根据key判断出该存放在数组的哪个下标
        //定义一个cur节点是这个数组的下标也就是链表的头节点去遍历这个链表
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) { //如果key值相等就把key的值进行更新
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //cur为空了
        //采用头插法进行插入
        Node node = new Node(key,val);
        node.next = array[index];
        array[index] = node;
        useSize++;
        //看是否满足负载因子
        if (calculateLoadFactor() >= LOAD_FCTOR) {
            //进行扩容  注：在扩容的时候，数组中的数据可能不满足映射关系了
            resize();
        }
    }

    public void resize() {
        Node[] newArray = new Node[2 * array.length];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                Node curNext = cur.next;
                //重新计算每一个key对应的哈希函数
                int index = cur.key % newArray.length;
                //先绑上边
                cur.next = newArray[index];
                //再绑下边
                newArray[index] = cur;
                //绑完再头插下一个
                cur = curNext;
            }
        }
        //新的数组给到原来的数组
        array = newArray;
    }
    //计算负载因子
    public double calculateLoadFactor() {
        return useSize*1.0 / array.length;
    }

    //取出key对应的val值
    public int get(int key) {
        //把key给进来之后就可以用哈希函数计算key所对应的下标（下标就是头节点）
        int index = key % array.length;
        Node cur = array[index];
        //然后再从头节点开始遍历
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
    //复制一个带随机指针的链表  有一个next域，有一个random域，这个随即域可能指向链表中的任意一个节点
    //                      也可能没有，也肯可能指向自己，总之是随机的
    //思路： 用Map来映射老链表和新链表的关系，key的值来存放老链表的节点，value存放新节点的链表
    //      每一个老节点都对应这一个新的节点，然后遍历两次数组，第一次遍历先把节点的val值放入新链表
    //       第二遍把结构对应好
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {//第一遍遍历先把值给新链表
            //Node node = new Node(cur.val);
            cur.val = map.get(cur).val;
            //map.put(cur,node);//map中存放的key值是老的节点，value值是新的节点
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {//第二遍遍历把结构对应好
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    //宝石和石头   jewels=”aA“；  stones=”aAAbbbbbb“；   宝石的数量就是3
    public int numJewelsInStones(String jewels, String stones) {
        int count = 0;
        Set<Character> set = new HashSet<>();//没有涉及到比较，不用TreeSet
        for (int i = 0; i < jewels.length(); i++) {
            set.add(jewels.charAt(i));  //把类型放入set集合中
        }
        for (int i = 0; i < stones.length(); i++) {
            if (set.contains(stones.charAt(i))) {
                count++;
            }
        }
        return count;
    }


}
